// 递归
// 本质是：解决主问题时，发现相同子问题，解决主问题和子问题的方法相同 (主问题有可能就是子问题)
// 心理暗示：宏观看待递归问题，把递归函数当成黑盒，相信这个黑盒一定能完成任务
// 技巧：
//      找到重复子问题 -> 设计函数头
//      子问题是如何解决的 -> 函数体的书写
//      注意递归函数的出口 -> 关注问题不能分割的情况
// 拓展：如果一个题目可以用决策树画出来，那么也可以通过递归解决

// 例题 5：
// 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
//
//        示例 1：
//
//        输入：x = 2.00000, n = 10
//        输出：1024.00000
//        示例 2：
//
//        输入：x = 2.10000, n = 3
//        输出：9.26100
//        示例 3：
//
//        输入：x = 2.00000, n = -2
//        输出：0.25000
//        解释：2-2 = 1/22 = 1/4 = 0.25
//
//
//        提示：
//
//        -100.0 < x < 100.0
//        -231 <= n <= 231-1
//        n 是一个整数
//        要么 x 不为零，要么 n > 0 。
//        -104 <= xn <= 104

// 解题思路：
// 先求 num = pow(x, n / 2)
// 再求 num * num
// 注意：n 有可能是负数

public class MyPow {
    public double myPow(double x, int n) {
        if(n == 0) return 1.0;
        double num = myPow(x, n / 2);
        if(n >= 0){
            return n % 2 == 0 ? num * num : num * num * x;
        }else{
            return n % 2 == 0 ? num * num : num * num / x;
        }
    }
}
